package com.gxd.item_902;

/**
 * 我们有一组排序的数字 D，它是  {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）
 *
 * 现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
 *
 * 返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/numbers-at-most-n-given-digit-set
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String S = String.valueOf(n);
        int K = S.length();
        int[] dp = new int[K + 1];
        dp[K] = 1;

        for (int i = K - 1; i >= 0; --i) {
            int Si = S.charAt(i) - '0';
            for (String d: digits) {
                if (Integer.parseInt(d) < Si) {
                    // 当前遍历的位数对应的值小于给定的值的对应位数的值时,低于此位的那几位可以随意取值
                    dp[i] += Math.pow(digits.length, K - i - 1);
                } else if (Integer.parseInt(d) == Si) {
                    // 相同时,此时能取的情况与上一位能取的情况相同
                    dp[i] += dp[i + 1];
                }
            }
        }

        for (int i = 1; i < K; ++i) {
            dp[0] += Math.pow(digits.length, i);
        }
        return dp[0];
    }
}
